| 翻訳と辞書 |
| extremal graph theory ： ウィキペディア英語版 |
extremal graph theory
Extremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal (maximal or minimal) graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth. More abstractly, it studies how global properties of a graph influence local substructures of the graph.
==Examples==
For example, a simple extremal graph theory question is "which acyclic graphs on ''n'' vertices have the maximum number of edges?" The extremal graphs for this question are trees on ''n'' vertices, which have ''n'' − 1 edges. More generally, a typical question is the following: given a graph property ''P'', an invariant ''u'', and a set of graphs ''H'', we wish to find the minimum value of ''m'' such that every graph in ''H'' which has ''u'' larger than ''m'' possess property ''P''. In the example above, ''H'' was the set of ''n''-vertex graphs, ''P'' was the property of being cyclic, and ''u'' was the number of edges in the graph. Thus every graph on ''n'' vertices with more than ''n'' − 1 edges must contain a cycle.
Several foundational results in extremal graph theory are questions of the above-mentioned form. For instance, the question of how many edges an ''n''-vertex graph can have before it must contain as subgraph a clique of size ''k'' is answered by Turán's theorem. Instead of cliques, if the same question is asked for complete multi-partite graphs, the answer is given by the Erdős–Stone theorem.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「extremal graph theory」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|